package org.lql.algo.codecrush.hot100.skill;

import java.util.Arrays;

/**
 * @author: liangqinglong
 * @date: 2025-10-13 22:46
 * @description: 31. 下一个排列 <a href="https://leetcode.cn/problems/next-permutation/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class NextPermutation {

	public void nextPermutation(int[] nums) {
		int n = nums.length;
		int i = n - 2;

		// 1. 从右往左找到第一个下降点 i
		while (i >= 0 && nums[i] >= nums[i + 1]) {
			i--;
		}

		// 2. 如果找到了 i（说明不是最后一个排列）
		if (i >= 0) {
			int j = n - 1;
			// 从右往左找到第一个比 nums[i] 大的数
			while (j >= 0 && nums[j] <= nums[i]) {
				j--;
			}
			// 交换 i 和 j
			swap(nums, i, j);
		}

		// 3. 反转 i 右边的部分
		reverse(nums, i + 1, n - 1);

		System.out.println(Arrays.toString(nums));
	}

	private void swap(int[] nums, int i, int j) {
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}

	private void reverse(int[] nums, int left, int right) {
		while (left < right) {
			swap(nums, left++, right--);
		}
	}

	public static void main(String[] args) {
		NextPermutation nextPermutation = new NextPermutation();
		nextPermutation.nextPermutation(new int[]{1, 2, 3});
		nextPermutation.nextPermutation(new int[]{3, 2, 1});
		nextPermutation.nextPermutation(new int[]{1, 1, 5});
	}
}
